package lru

import "container/list"

// Cache 是LRU缓存。并发访问是不安全的
type Cache struct {
	maxBytes int64                    // 允许使用的最大内存，超过该大小会采用淘汰策略
	nBytes   int64                    // 当前已经使用的内存大小
	ll       *list.List               // 双向链表存储缓存数据
	cache    map[string]*list.Element // 字典，值是双向链表中对应节点的指针
	// 可选，清理条目时调用
	onEvicted func(key string, value Value) // 记录被移除时的回调函数
}

type entry struct {
	key   string
	value Value
}

type Value interface {
	Len() int
}

func New(maxBytes int64, onEvicted func(string, Value)) *Cache {
	return &Cache{
		maxBytes: maxBytes,
		// nBytes:    0,
		ll:        list.New(),
		cache:     make(map[string]*list.Element),
		onEvicted: onEvicted,
	}
}

func (c *Cache) Get(key string) (value Value, ok bool) {
	if ele, ok := c.cache[key]; ok {
		// 已存在，节点移动到队尾。（队首的节点会被优先淘汰）
		c.ll.MoveToFront(ele)
		kv := ele.Value.(*entry)
		return kv.value, true
	}
	return
}

func (c *Cache) RemoveOldest() {
	// 取队首节点删除
	ele := c.ll.Back()
	if ele != nil {
		c.ll.Remove(ele)
		kv := ele.Value.(*entry)
		delete(c.cache, kv.key)
		c.nBytes -= int64(len(kv.key)) + int64(kv.value.Len())
		// 	回调函数
		if c.onEvicted != nil {
			c.onEvicted(kv.key, kv.value)
		}
	}
}

func (c *Cache) Add(key string, val Value) {
	if ele, ok := c.cache[key]; ok {
		// 已存在，节点移动到队尾。（队首的节点会被优先淘汰）
		c.ll.MoveToFront(ele)
		kv := ele.Value.(*entry)
		// 已用内存，此处计算新增的内存
		c.nBytes += int64(val.Len()) - int64(kv.value.Len())
		kv.value = val
	} else {
		ele := c.ll.PushFront(&entry{
			key:   key,
			value: val,
		})
		c.cache[key] = ele
		c.nBytes += int64(len(key)) + int64(val.Len())
	}
	// 判断是否超过设定的最大值maxBytes
	for c.maxBytes != 0 && c.maxBytes < c.nBytes {
		c.RemoveOldest()
	}
}

// Len Value接口实现
func (c *Cache) Len() int {
	return c.ll.Len()
}
